package hot100;

public class productExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        //通过前缀积和后缀积来计算即i之前数字的乘积*i之后数字的乘积
        int n = nums.length;
        int[] ret = new int[n];
        int[] pretab = new int[n];
        int[] aftab = new int[n];
        pretab[0] = 1;
        aftab[n-1] = 1;
        //前缀积
        for(int i = 1;i < n;i++) {
            pretab[i] = pretab[i-1]*nums[i-1];
        }
        //后缀积
        for(int j = n - 2;j >= 0;j--) {
            aftab[j] = aftab[j+1]*nums[j+1];
        }
        for(int i = 0;i < n;i++) {
            ret[i] = pretab[i] * aftab[i];
        }
        return ret;
    }
}
